
#ifndef _CILK_
#define cilk_for for
#endif

#include "Game.h"
#include <vector>
#include "limits.h"
#include <stdlib.h>
#include <iostream>
#include <string>



#define SEARCH_DEPTH 4
#define VALIDATE_MOVES true

Game::Game(string boardLayout, bool alphabeta) : currentBoard(Board(boardLayout))
{
    currentPly = 0;
    using_alphabeta = alphabeta;
}

Game::~Game() {
}

Game::Game(const Game& orig)
{
    currentPly = orig.currentPly;
    currentBoard = orig.currentBoard;
    using_alphabeta = orig.using_alphabeta;
}

// Called to perform a move for the CPU (abstraction method)
game_result Game::cpuMove()
{
    game_result status = IN_PROGRESS;

    if(using_alphabeta)
        status = alphaBetaBase(currentPly, SEARCH_DEPTH);
    else
        status = minMaxBase(currentPly, SEARCH_DEPTH);
    return status;
}

// Call to perform a move for the human player
game_result Game::humanMove(int frow, int fcol, int trow, int tcol)
{
    int status;
    
    // Process the human player's move
    Board tempBoard = currentBoard;
    movePiece(frow, fcol, trow, tcol);
    if(VALIDATE_MOVES && !validateMove(tempBoard))
    {
        currentBoard = tempBoard;
        cout << "!--Invalid move--!" << endl;
        return IN_PROGRESS;
    }

    currentPly++;

    // Process the CPU move and return
    std::cout << endl << "Thinking..." << endl << endl;

    // Perform the AI's next move
    status = 0;
    //status = cpuab(currentPly, SEARCH_DEPTH);
    cpuMove();
    currentPly++;

    // If the AI was able to move succesfully, check if the player has any valid moves
    if(status == 0)
        status = checkGameStatus();
        

    return status;
}

void Game::castle(bool playerIsWhite, bool kingside)
{
	currentBoard.castle(playerIsWhite, kingside);
	currentPly++;
	std::cout << endl << "Thinking..." << endl;
	cpuMove();
	currentPly++;
}

// Uses the min max algorithm to return the value of certain moves
int Game::minmax(Board *board, int ply, int depth)
{
    int moveValue, numMoves;
    std::vector<Board*> moves;
    int max = INT_MIN;

    // If this is a leaf node, evaluate the board and return
    if(depth == 0)
        return board->evaluate();
    // Get a list of all possible moves from this board
    board->generateMoves(moves, ply);
    // Check all of the moves via the minmax algorithm
    numMoves = moves.size();    
    for(int i=0; i<numMoves; i++)
    {
        Board *potentialMove = moves.back();
        moveValue = minmax(potentialMove, ply+1, depth-1);
        // If black, invert the result, effectively making the next step take the minimum
        if(ply % 2 == 1)
            moveValue = -moveValue;
        // If white, find the maximum value, or if black, find the minimum
        if(moveValue > max)
            max = moveValue;

        moves.pop_back();
        delete potentialMove;
    }

    // If no moves were valid, check for checkmate
    if(numMoves == 0)
    {
        if(board->isInCheck(BLACK))
            return INT_MAX;
        if(board->isInCheck(WHITE))
            return INT_MIN;
    }

    // If black, invert the result, otherwise, return the best value found
    if(ply %2 == 1)
        return -max;
    return max;
}

// Prints the game board
void Game::printGame()
{    
    currentBoard.printBoard();
}


int Game::alphaBeta(Board *board, int ply, int depth, int alpha, int beta)
{
    int numMoves;
    Board *potentialMove;
    std::vector<Board*> moves;

    // If this is a leaf node, evaluate the board and return
    if(depth == 0)
        return board->evaluate();

    board->generateMoves(moves, ply);
    numMoves = moves.size();
    // Explore all child nodes
    for(int i=0; i<numMoves; i++)
    {
        potentialMove = moves.back();
        // Update alpha and beta according to whos turn it is
        if(ply % 2 == 0)
            alpha = max(alpha, alphaBeta(potentialMove, ply+1, depth-1, alpha, beta));
        else
            beta = min(beta, alphaBeta(potentialMove, ply+1, depth-1, alpha, beta));
        // Cutoffs (alpha and beta), this block of code does not distinguish between them
        
        if(beta <= alpha)
        {
            //  Clear the remaining moves in the list
            while(!moves.empty())
            {
                Board *move = moves.back();
                moves.pop_back();
                delete move;
            }
            break;
        }
        
        moves.pop_back();
        delete potentialMove;
    }

    if(ply % 2 == 0)
        return alpha;
    return beta;
}

game_result Game::alphaBetaBase(int ply, int depth)
{
    int numMoves, maxIndex, max = INT_MIN;
    int *scores;
    std::vector<Board*> moves;

    int alpha = INT_MIN, beta = INT_MAX;
    
    // Calculate the next set of moves
    currentBoard.generateMoves(moves, ply);
    numMoves = moves.size();
    if(numMoves == 0)
        return noCPUMoves();

    cout << "Solving " << numMoves << " moves: ";
    scores = new int[numMoves];
    cilk_for(int i=0; i<numMoves; i++)
    {
        Board *potentialMove = moves.at(i);
        scores[i] = alphaBeta(potentialMove, ply+1, depth-1, alpha, beta);
        
        if(scores[i] > alpha)
            alpha = scores[i];

        cout << "|" << flush;
    }
    cout << endl;

    // Find the best move based on its score ((Serial))
    for(int i=0; i<numMoves; i++)
    {
        if(scores[i] > max)
        {
            max = scores[i];
            maxIndex = i;
        }
    }

    // Use the best move found
    currentBoard = *(moves.at(maxIndex));

    // Free allocated memory
    delete scores;
    for(int i=0; i<numMoves; i++)
    {
        Board* temp = moves.back();
        moves.pop_back();
        delete temp;
    }
    return IN_PROGRESS;
}

// Move a game piece
void Game::movePiece(int frow, int fcol, int trow, int tcol)
{
    // If a human move, check for promotion
    if(currentPly % 2 == 1)
    {
        // The human is black
        if(currentBoard.pieces[frow][fcol] == BLACK*PAWN && trow == 0)
        {
            currentBoard.pieces[frow][fcol] = EMPTY;
            currentBoard.pieces[trow][tcol] = BLACK*humanPromotion();
            return;
        }
    }

    currentBoard.pieces[trow][tcol] = currentBoard.pieces[frow][fcol];
    // Remove the piece from the starting position
    currentBoard.pieces[frow][fcol] = EMPTY;

}

game_result Game::checkGameStatus()
{
    // Check if the human player has any moves
    std::vector<Board *> humanMoves;
    currentBoard.generateMoves(humanMoves, currentPly);

    bool humanInCheck(currentBoard.isInCheck(BLACK)); // TODO

    if(humanMoves.empty())
    {
        if(humanInCheck)
        {
            cout << "!<<Checkmate>>!" << endl;
            return WHITE_WINS; // TODO
        }
        else
        {
            cout << "<<Stalemat>>" << endl;
            return STALEMATE;
        }
    }
    else
    {
        if(humanInCheck)
        {
            cout << "<Check>" << endl;
        }
        return IN_PROGRESS;
    }
}

game_result Game::startGame(int player)
{
    game_result status;
    // TODO
    if(player == WHITE)
    {
        // Perform the AI's next move       
        status = cpuMove();
        currentPly++;

        // If the AI was able to move succesfully, check if the player has any valid moves
        if(status == IN_PROGRESS)
            status = checkGameStatus();
    }
    else
    {
        // Wait for human move
        status = IN_PROGRESS;
    }
    return status;
}

game_result Game::minMaxBase(int ply, int depth)
{
    int max = INT_MIN;
    int numMoves, maxIndex;
    int *scores;
    
    std::vector<Board*> moves;

    // Calculate the next set of moves
    currentBoard.generateMoves(moves, ply);
    numMoves = moves.size();
    if(numMoves == 0)
        return noCPUMoves();

    cout << "Solving " << numMoves << " moves: ";
    // Calculate all of the scores for our set of potential moves ((Parallel))
    scores = new int[numMoves];
    cilk_for(int i=0; i<numMoves; i++)
    {
        Board *potentialMove;
        potentialMove = moves.at(i);
        scores[i] = minmax(potentialMove, ply+1, depth-1);
        cout << "|" << flush;

    }
    cout << endl;

    // Find the best move based on its score ((Serial))
    for(int i=0; i<numMoves; i++)
    {
        if(scores[i] > max)
        {
            max = scores[i];
            maxIndex = i;
        }
    }
    cout << endl << max << endl;
    // Use the best move found
    currentBoard = *(moves.at(maxIndex));
    
    // Free allocated memory
    delete scores;
    for(int i=0; i<numMoves; i++)
    {
        Board* temp = moves.back();
        moves.pop_back();
        delete temp;
    }

    return IN_PROGRESS;
}


game_result Game::noCPUMoves()
{
    // If the CPU was in check on the last move, this is check mate
    if(currentBoard.status == WHITE_CHECK)
    {
        cout << "Congratulations, you've won!" << endl;
        return BLACK_WINS;
    }
    else
    {
        cout << "<<Stalemate>>" << endl;
        return STALEMATE;
    }
}

piecetype Game::humanPromotion()
{
    char input;
    piecetype newpiece = EMPTY;

    do
    {
        cout << "Enter piece to promote to (q, r, n, b):" << endl;
        cin >> input;

        if(input == 'q')
            newpiece = QUEEN;
        else if(input == 'r')
            newpiece = ROOK;
        else if(input == 'n')
            newpiece = KNIGHT;
        else if(input == 'b')
            newpiece = BISHOP;
        else
            cout << "Input not recognized. >>> ";
    } while(newpiece == EMPTY);
    return newpiece;
}

bool Game::validateMove(Board board)
{
    vector<Board *> possibleMoves;
    board.generateMoves(possibleMoves, currentPly);

    bool result = false;
    Board *possibleBoard;
    // Check if one of the generated moves matches the human made move
    while(!possibleMoves.empty())
    {
        possibleBoard = possibleMoves.back();
        if(*possibleBoard == currentBoard)
            result = true;

        possibleMoves.pop_back();
        delete possibleBoard;
    }
    
    return result;
}